Communication networks are often modeled as an open system interconnected seven layer reference model. Layer 3 (network layer, e.g., routers) and Layer 2 (data link layer, e.g., switches, bridges, and hubs) are particularly important layers with respect to overall network performance and vulnerability. Layers 2 and 3 are further characterized by the “topology” of the layer, i.e., a set of devices and the connections between them. Knowledge of the topography of a layer is of particular importance in network management tasks such as failure analyses and isolating locations in a network that have been infected by worms propagated over the internet.
Topology discovery has been studied at various levels, including layer 2 Ethernet topology discovery, to provide a capability to reconstruction layer topology of an existing network. There have been several discovery algorithms studied for recovering layer 2 Ethernet topologies from information collected from simple network management protocols (SNMP). Breitbart, et al., “Topology Discovery in Heterogeneous IP Networks,” Proceedings of IEEE INFOCOM, 2000, pp. 265-274, take the approach of assuming all nodes are connected and then identifying contradictory information. Lowekamp et al., “Topology Discovery for Large Ethernet Networks,” Proceedings of ACMSIGCOMM, August 2001, pp. 237-248, uses a similar approach with a focus on incomplete (not fully propagated) forwarding tables. Most recently, Bejerano, et al., “Physical Topology Discovery for Large Multi-Subnet Networks,” Proceedings of IEEE INFOCOM, 2003, provide more complex algorithms with a guarantee of recovering all available information from the raw data. David T. Stott, “Layer-2 Path Discovery Using Spanning Tree Mibs,” Tech. Rep. ALR-2002-004, March 2002, teaches an approach that uses SNMP access to the results of the Spanning Tree Protocol that is run on each switch.
Topology reconstruction may be used to determine quality of service problems that might arise from the deployment of internet protocol (IP) telephony on actual networks. The ability to reconstruct topologies also may be used extensively in commercial network management systems.
Various objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.